class Solution {
public:
    vector<int> stk;
    vector<vector<int>> ans;
    void dfs(int l,int r,int k)
    {
        if(k==0)
        {
            ans.push_back(stk);
            return;
        }
        for(int i=l;i<=r;i++)
        {
            stk.push_back(i);
            dfs(i+1,r,k-1);
            stk.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        // vector<vector<int>> ans;
        // for(int i=0;i<(1<<(n+1));i++)
        // {
        //     vector<int> temp;
        //     for(int j=0;j<=n;j++)
        //     {
        //         if(i&(1<<j))
        //         {
        //             if(j==0)
        //                 break;
        //             temp.push_back(j);
        //         }
        //     }
        //     if(temp.size()==k)
        //         ans.push_back(temp);
        // }
        // return ans;
        
        //深度优先搜索（一）组合
        stk.clear();
        dfs(1,n,k);
        return ans;

    }
};